//A union-find algorithm to detect cycle in a graph
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

//a structure to represent an edge in graph
typedef struct edge
{
    int src, dest;
} Edge;

typedef struct graph
{
    //顶点和边的数量
    int nV, nE;
    Edge *edge;
} Graph;

typedef struct sub_set
{
    int parent;
    int rank;
} SubSet;

Graph *
createGraph(int nV, int nE)
{
    Graph *graphP = malloc(sizeof(*graphP));
    if (graphP != NULL)
    {
        graphP->nE = nE;
        graphP->nV = nV;
        graphP->edge = malloc(nE * sizeof(*graphP->edge));
    }
    return graphP;
}

//A utility function to find the subset of an element i
int find(SubSet subSets[], int i)
{
    if (subSets[i].parent != i)
        subSets[i].parent = find(subSets, subSets[i].parent);
    //path compression
    return subSets[i].parent;
}

//A utility function to do union of two subsets
//(use union by rank)
//the union must be a whole set
void Union(SubSet subSets[], int x, int y)
{
    int xset = find(subSets, x);
    int yset = find(subSets, y);
    if (subSets[xset].rank < subSets[yset].rank)
        subSets[xset].parent = yset;
    else if (subSets[xset].rank > subSets[yset].rank)
        subSets[yset].parent = xset;
    else
    {
        //only maintain the root rank
        //只需要维护root节点的rank，即知道树的总深度即可
        subSets[yset].parent = xset;
        subSets[xset].rank++;
    }
}

//The main function to check whether a given graph contains cycle or not
int isCycle(Graph *graphP)
{
    SubSet *subSets = malloc(graphP->nV * sizeof(*subSets));
    if (subSets == NULL)
    {
        return -1;
    }

    for (int i = 0; i < graphP->nV; i++)
    {
        subSets[i].parent = i;
        subSets[i].rank = 0;
    }
    //iterate through all edges of graph, find subset of both
    //vertices of every edge, if both subsets are samem, then there is a cycle in gragh.
    for (int i = 0; i < graphP->nE; i++)
    {

        int x = find(subSets, graphP->edge[i].src);
        int y = find(subSets, graphP->edge[i].dest);
        if (x == y)
        {
            return 1;
        }
        Union(subSets, x, y);
    }

    return 0;
}

int main(int argc, char **argv)
{
    int nV = 4, nE = 4;
    Graph *graphP = createGraph(nV, nE);
    if (graphP == NULL)
    {
        printf("createGraph error\n");
        exit(EXIT_FAILURE);
    }

    graphP->edge[0].src = 0;
    graphP->edge[0].dest = 1;
    graphP->edge[1].src = 1;
    graphP->edge[1].dest = 2;
    graphP->edge[2].src = 2;
    graphP->edge[2].dest = 3;
    graphP->edge[3].src = 3;
    graphP->edge[3].dest = 0;

    if (isCycle(graphP))
    {
        printf("graph contains cycle\n");
    }
    else
    {
        printf("graph doesn't contain cycle\n");
    }
    return 0;
}